Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with "sufficiently many edges" must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of any two non-adjacent vertices: if this sum is always at least equal to the total number of vertices in the graph, then the graph is Hamiltonian.
Contents |
Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if
then G is Hamiltonian.
Suppose it were possible to construct a graph that fulfils condition (*) which is not Hamiltonian. According to this supposition, let G be a graph on n ≥ 3 vertices that satisfies property (*), is not Hamiltonian, and has the maximum possible number of edges among all n-vertex non-Hamiltonian graphs that satisfy property (*). Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v1v2...vn, for otherwise it would be possible to add edges to G without breaching property (*). Since G is not Hamiltonian, v1 cannot be adjacent to vn, for otherwise v1v2...vn would be a Hamiltonian cycle. By property (*), deg v1 + deg vn ≥ n, and the pigeon hole principle implies that for some i in the range 2 ≤ i ≤ n − 1, vi is adjacent to v1 and vi − 1 is adjacent to vn. But the cycle v1v2...vi − 1vnvn − 1...vi is then a Hamilton cycle. This contradiction yields the result.
Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.
Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether vj and vj + 1 are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph. By an argument similar to the one in the proof of the theorem, the desired index j must exist, or else the nonadjacent vertices vi and vi + 1 would have too small a total degree. Finding i and j, and reversing part of the cycle, can all be accomplished in time O(n). Therefore, the total time for the algorithm is O(n2), matching the number of edges in the input graph.
Ore's theorem is a generalization of Dirac's theorem that, when each vertex has degree at least n/2, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least n.
In turn Ore's theorem is generalized by the Bondy–Chvátal theorem. One may define a closure operation on a graph in which, whenever two nonadjacent vertices have degrees adding to at least n, one adds an edge connecting them; if a graph meets the conditions of Ore's theorem, its closure is a complete graph. The Bondy–Chvátal theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian; since the complete graph is Hamiltonian, Ore's theorem is an immediate consequence.
Woodall (1972) found a version of Ore's theorem that applies to directed graphs. Suppose a digraph G has the property that, for every two vertices u and v, either there is a vertex from u to v or the outdegree of u plus the indegree of v equals or exceeds the number of vertices in G. Then, according to Woodall's theorem, G contains a directed Hamiltonian cycle. Ore's theorem may be obtained from Woodall by replacing every edge in a given undirected graph by a pair of directed edges.
Ore's theorem may also be strengthened to give a stronger condition than Hamiltonicity as a consequence of the degree condition in the theorem. Specifically, every graph satisfying the conditions of Ore's theorem is either a regular complete bipartite graph or is pancyclic (Bondy 1971).